#include<bits/stdc++.h>
#define sd(n) scanf("%d",&n) 
#define sld(n) scanf("%lld",&n)
#define pd(n) printf("%d", (n))
#define pld(n) printf("%lld", n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fi first
#define se second
const int N=2e5;
#define INF 0x7fffffff
typedef long long int ll;
using namespace std;
//----------------------------------------------------------------------------//
template <typename _Tp, typename _Fp, typename _Compare = std::less<void>>
bool chmin(_Tp &a, const _Fp &b, _Compare __comp = _Compare()) { return __comp(b, a) ? a = b, true : false; }
template <typename _Tp, typename _Fp, typename _Compare = std::less<void>>
bool chmax(_Tp &a, const _Fp &b, _Compare __comp = _Compare()) { return __comp(a, b) ? a = b, true : false; }
namespace OY {
    template <typename _Tp>
    struct BellmanFord {
        struct _Edge {
            uint32_t from, to;
            _Tp distance;
        };
        std::vector<_Edge> m_edges;
        std::vector<_Tp> m_distances;
        std::vector<uint32_t> m_from;
        uint32_t m_vertexNum;
        _Tp m_infiniteDistance;
        BellmanFord(uint32_t __vertexNum, uint32_t __edgeNum, _Tp __infiniteDistance = std::numeric_limits<_Tp>::max() / 2) : m_distances(__vertexNum, __infiniteDistance), m_vertexNum(__vertexNum), m_infiniteDistance(__infiniteDistance) { m_edges.reserve(__edgeNum); }
        void addEdge(uint32_t __a, uint32_t __b, _Tp __distance) { m_edges.push_back({__a, __b, __distance}); }
        void setDistance(uint32_t __i, _Tp __distance = 0) { m_distances[__i] = __distance; }
        template <bool _GetPath = false>
        bool calc() {
            if constexpr (_GetPath) m_from.resize(m_vertexNum, -1);
            uint32_t lastUpdate = -1;
            for (uint32_t i = 0; i < m_vertexNum && lastUpdate == i - 1; i++)
                for (uint32_t index = 0; index < m_edges.size(); index++)
                    if (auto &[from, to, distance] = m_edges[index]; m_distances[from] != m_infiniteDistance && chmin(m_distances[to], m_distances[from] + distance)) {
                        lastUpdate = i;
                        if constexpr (_GetPath) m_from[to] = index;
                    }
            return lastUpdate != m_vertexNum - 1;
        }
        std::vector<uint32_t> getPath_edge(uint32_t __target) const {
            std::vector<uint32_t> path;
            for (uint32_t cur = __target; ~m_from[cur]; cur = m_edges[m_from[cur]].from) path.push_back(m_from[cur]);
            std::reverse(path.begin(), path.end());
            return path;
        }
        std::vector<uint32_t> getPath_vertex(uint32_t __target) const {
            std::vector<uint32_t> path;
            path.push_back(__target);
            for (uint32_t cur = __target; ~m_from[cur];) path.push_back(cur = m_edges[m_from[cur]].from);
            std::reverse(path.begin(), path.end());
            return path;
        }
    };
}

int main() {
    //有向图
    OY::BellmanFord<int> G1(4, 3);
    //加三条边
    G1.addEdge(0, 1, 100);
    G1.addEdge(1, 2, -30);
    G1.addEdge(2, 3, 70);
    //设置好源点距离
    G1.setDistance(0, 0);
    //求最短路，检查有无负圈
    if (!G1.calc<true>()) {
        cout << "has negative cycle\n";
    } else {
        cout << "no negative cycle\n";
        cout << "min distance from 0 to 3 is: " << G1.m_distances[3] << endl;
        auto vertex_path = G1.getPath_vertex(3);
        cout << "min_distance_path from 0 to 3 is:\n";
        for (auto i : vertex_path)
            cout << i << endl;
    }

    //无向图
    OY::BellmanFord<int> G2(4, 8);
    //加四对边
    G2.addEdge(0, 1, 100);
    G2.addEdge(1, 0, 100);
    G2.addEdge(0, 2, 30);
    G2.addEdge(2, 0, 30);
    G2.addEdge(2, 1, 60);
    G2.addEdge(1, 2, 60);
    G2.addEdge(1, 3, 70);
    G2.addEdge(3, 1, 70);
    //设置好源点距离
    G2.setDistance(0, 0);
    //求最短路，检查有无负圈
    if (!G2.calc<true>()) {
        cout << "has negative cycle\n";
    } else {
        cout << "no negative cycle\n";
        cout << "min distance from 0 to 3 is: " << G2.m_distances[3] << endl;
        auto edge_path = G2.getPath_edge(3);
        cout << "min_distance_path from 0 to 3 is:\n";
        for (auto i : edge_path) {
            auto [from, to, distance] = G2.m_edges[i];
            cout << from << "->" << to << endl;
        }
    }
}